'''
n个格子，m种颜料
图完n个格子，用完m种颜料，算一种图法
'''
from functools import cache


def fff(n, m):
    # i: 图了多少格子, j: 用了多少颜料
    @cache
    def f(i, j):
        if i == n: return 1 if j == m else 0
        if j == m: return (n - i) * m   # 提前完成，剩下随意组合
        res1 = j * f(i+1, j)            # 不用新颜料，这个格子的图法
        res2 = (m - j) * f(i+1, j+1)    # 用新颜料这个格子的图法
        return res1 + res2

# dp打表
# 依赖 下边 和 右下边
# 从下往上，从右往左
# 初始格子 i == n: dp[n][m] = 1                 # dp[n][j] = 1 if j == m else 0  # dp[n][m] = 1
#         j == m: dp[i][m] = (n - i) * m
# 普遍位置: dp[i][j] = j * dp[i+1][j] + (m - j) * dp[i+1][j+1]
pass